{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #N-ary Tree Level Order Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #breadth-first-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #广度优先搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: levelOrder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #N 叉树的层序遍历"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个 N 叉树，返回其节点值的<em>层序遍历</em>。（即从左到右，逐层遍历）。</p>\n",
    "\n",
    "<p>树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2018/10/12/narytreeexample.png\" style=\"width: 100%; max-width: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,null,3,2,4,null,5,6]\n",
    "<strong>输出：</strong>[[1],[3,2,4],[5,6]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/11/08/sample_4_964.png\" style=\"width: 296px; height: 241px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]\n",
    "<strong>输出：</strong>[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树的高度不会超过 <code>1000</code></li>\n",
    "\t<li>树的节点总数在 <code>[0, 10^4]</code> 之间</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [n-ary-tree-level-order-traversal](https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [n-ary-tree-level-order-traversal](https://leetcode.cn/problems/n-ary-tree-level-order-traversal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,null,3,2,4,null,5,6]', '[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'Node') -> List[List[int]]:\n",
    "        if root is None: return []\n",
    "        levels, level = [], 0\n",
    "        queue = deque([root])\n",
    "        \n",
    "        while queue:\n",
    "            levels.append([])\n",
    "            for _ in range(len(queue)):\n",
    "                curr = queue.popleft()\n",
    "                levels[level].append(curr.val)\n",
    "                \n",
    "                for child in curr.children:\n",
    "                    queue.append(child)\n",
    "            level += 1\n",
    "        return levels\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, children):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def levelOrder(self, root):\n",
    "        \"\"\"\n",
    "        :type root: Node\n",
    "        :rtype: List[List[int]]\n",
    "       \"\"\"\n",
    "        \n",
    "        if not root:\n",
    "            return []\n",
    "        res,cur_level = [],[root]\n",
    "        while cur_level:\n",
    "            next_level,tmp_res=[],[]\n",
    "            for node in cur_level:\n",
    "                tmp_res.append(node.val)\n",
    "                for child in node.children:\n",
    "                    next_level.append(child)\n",
    "            res.append(tmp_res)\n",
    "            cur_level = next_level\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, children):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        res=[]\n",
    "        tree=[root]\n",
    "        while tree :\n",
    "            restemp=[]\n",
    "            tretemp=[]\n",
    "            for i in tree:\n",
    "                restemp.append(i.val)\n",
    "                tretemp.extend(i.children)\n",
    "            res.append(restemp)\n",
    "            tree=tretemp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, children):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "from queue import Queue\n",
    "class Solution:\n",
    "    def levelOrder(self, root):\n",
    "        \"\"\"\n",
    "        :type root: Node\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return []\n",
    "        q = Queue()\n",
    "        q.put(root)\n",
    "        q.put('#')\n",
    "        ret = []\n",
    "        row = []\n",
    "        while not q.empty():\n",
    "            top =  q.get()\n",
    "            if top != '#':\n",
    "                row.append(top.val)\n",
    "                if not not top.children:\n",
    "                    for i in top.children:\n",
    "                        q.put(i)\n",
    "                    \n",
    "            else:\n",
    "                ret.append(row)\n",
    "                row = []\n",
    "                if not q.empty():\n",
    "                    q.put(\"#\")\n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, children):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'Node') -> List[List[int]]:\n",
    "        if root == None:\n",
    "            return []\n",
    "        res = [[root.val]]\n",
    "        t = []\n",
    "        t.append(root)\n",
    "        while(t!=[]):\n",
    "            tmp = []\n",
    "            tmp_val = []\n",
    "            for i in t:\n",
    "                for j in range(len(i.children)):\n",
    "                    tmp_val.append(i.children[j].val)\n",
    "                    tmp.append(i.children[j])\n",
    "            if tmp_val!= []:\n",
    "                 res.append(tmp_val)\n",
    "            t = tmp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, children):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'Node') -> 'List[List[int]]':\n",
    "        if root==None:\n",
    "            return []\n",
    "        res=[[root.val]]\n",
    "        queue=[root]\n",
    "        while queue:\n",
    "            r=[]\n",
    "            for node in queue:\n",
    "                    r+=node.children\n",
    "            if r:\n",
    "                res.append([n.val for n in r])\n",
    "            queue=r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'Node') -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = collections.deque()\n",
    "        result=[]\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            levelsize = len(queue)\n",
    "            levellist = []\n",
    "            for _ in range(levelsize):\n",
    "                node = queue.popleft()\n",
    "                levellist.append(node.val)\n",
    "                for child in node.children:\n",
    "                    if child:\n",
    "                        queue.append(child)\n",
    "            result.append(levellist)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'Node') -> List[List[int]]:\n",
    "        result = []\n",
    "\n",
    "        def helper(node, level):\n",
    "            if node == None:\n",
    "                return\n",
    "            if len(result) > level:\n",
    "                result[level].append(node.val)\n",
    "            else:\n",
    "                result.append([node.val])\n",
    "\n",
    "            for child in node.children:\n",
    "                helper(child, level + 1)\n",
    "\n",
    "        helper(root, 0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'Node') -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "        cur = [root]\n",
    "        next_level = []\n",
    "        while cur:\n",
    "            res.append([i.val for i in cur])\n",
    "            for i in cur:\n",
    "                for j in i.children:\n",
    "                    next_level.append(j)\n",
    "            cur, next_level = next_level, []\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'Node') -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "        cur = [root]\n",
    "        next_level = []\n",
    "        while cur:\n",
    "            res.append([i.val for i in cur])\n",
    "            for i in cur:\n",
    "                for j in i.children:\n",
    "                    next_level.append(j)\n",
    "            cur, next_level = next_level, []\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'Node') -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        queue = [root]\n",
    "        res = []\n",
    "        while queue:\n",
    "            res.append(node.val for node in queue)\n",
    "            queue = [child for node in queue for child in node.children]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'Node') -> List[List[int]]:\n",
    "        # if not root:\n",
    "        #     return []\n",
    "        # res = []\n",
    "        # deque = collections.deque([root])\n",
    "        # while deque:\n",
    "        #     tmp = []\n",
    "        #     for i in range(len(deque)):\n",
    "        #         root = deque.popleft()\n",
    "        #         tmp.append(root.val)\n",
    "        #         for c in root.children:\n",
    "        #             deque.append(c)\n",
    "        #     res.append(tmp)\n",
    "        # return res\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        def level_(root,level):\n",
    "            if len(res)==level:\n",
    "                res.append([])\n",
    "            res[level].append(root.val)\n",
    "            for c in root.children:\n",
    "                level_(c,level+1)\n",
    "        res = []\n",
    "        if not root:\n",
    "            return []\n",
    "        level_(root,0)\n",
    "        return res\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'Node') -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue,ans,tempans = [root],[],[]\n",
    "        while queue:\n",
    "            nextqueue,tempans = [],[]\n",
    "            while queue:\n",
    "                node = queue.pop(0)\n",
    "                tempans.append(node.val)\n",
    "                if node.children:\n",
    "                    nextqueue.extend(node.children)\n",
    "            ans.append(tempans)\n",
    "            queue = nextqueue\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'Node') -> List[List[int]]:\n",
    "\n",
    "        def traverse_node(node, level):\n",
    "            if len(result) == level:\n",
    "                result.append([])\n",
    "            result[level].append(node.val)\n",
    "            for child in node.children:\n",
    "                traverse_node(child, level + 1)\n",
    "\n",
    "        result = []\n",
    "        if root is not None:\n",
    "            traverse_node(root, 0)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'Node') -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        queue = []\n",
    "        queue.append({\n",
    "            \"item\": root,\n",
    "            \"depth\": 0\n",
    "        })\n",
    "        result = []\n",
    "        while len(queue) is not 0:\n",
    "            node = queue[0]['item']\n",
    "            depth = queue[0]['depth']\n",
    "            #print(len(queue))\n",
    "            del queue[0]\n",
    "            if node.children is not None:\n",
    "                for i in node.children:\n",
    "                    queue.append({\n",
    "                       \"item\": i,\n",
    "                       \"depth\": depth + 1\n",
    "                    })\n",
    "            if depth >= len(result):\n",
    "                result.append([])\n",
    "            result[depth].append(node.val)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, children):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'Node') -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        q = queue.Queue()\n",
    "        q.put((root, 0))\n",
    "        dic = collections.defaultdict(list)\n",
    "        ans = []\n",
    "        max_level = -1\n",
    "        while not q.empty():\n",
    "            node, level = q.get()\n",
    "            dic[level].append(node.val)\n",
    "            max_level = max(max_level, level)\n",
    "            for child in node.children:\n",
    "                q.put((child, level+1))\n",
    "        for i in range(max_level+1):\n",
    "            ans.append([])\n",
    "        for key in sorted(dic):\n",
    "            for val in dic[key]:\n",
    "                ans[key].append(val)\n",
    "                print(val)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'Node') -> List[List[int]]:\n",
    "        # bfs 使用双端队列即可\n",
    "        if root is None:\n",
    "            return None\n",
    "        eles = collections.deque()\n",
    "        res = []\n",
    "        eles.append(root)\n",
    "        while eles:\n",
    "            sz = len(eles)\n",
    "            i = 0\n",
    "            cur_list = []\n",
    "            while i < sz:\n",
    "                cur = eles.popleft()\n",
    "                # 添加当前元素\n",
    "                if cur is None:\n",
    "                    continue\n",
    "                cur_list.append(cur.val)\n",
    "                if cur.children:\n",
    "                    for p in cur.children:\n",
    "                        eles.append(p)\n",
    "                i += 1\n",
    "            res.append(cur_list)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'Node') -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        result =[]\n",
    "        \n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            ans = []\n",
    "            for _ in range(size):\n",
    "                node = queue.popleft()\n",
    "                ans.append(node.val)\n",
    "                for children in node.children:\n",
    "                    queue.append(children)\n",
    "            result.append(ans)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'Node') -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        \n",
    "        node_list=[(root)]\n",
    "        result=[]\n",
    "        while node_list:\n",
    "            next_list=[]\n",
    "            vals=[]\n",
    "            for node in node_list:\n",
    "                if node.children:\n",
    "                    next_list.extend(list(node.children))\n",
    "                vals.append(node.val)\n",
    "            result.append(vals)\n",
    "            node_list=next_list\n",
    "        return result\n",
    "        \n",
    "                \n",
    "\n",
    "                \n",
    "        \n",
    "        \n",
    "                \n",
    "\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'Node') -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ans = []\n",
    "        de = deque()\n",
    "        de.append(root)\n",
    "        while de:\n",
    "            t = []\n",
    "            for _ in range(len(de)):\n",
    "                p = de.pop()\n",
    "                t.append(p.val)\n",
    "                for child in p.children:\n",
    "                    de.appendleft(child)\n",
    "            ans.append(t)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'Node') -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res1 = []\n",
    "        que = deque([root])\n",
    "        while que:\n",
    "            size = len(que)\n",
    "            res2 = []\n",
    "            for _ in range(size):\n",
    "                cur = que.popleft()\n",
    "                res2.append(cur.val)\n",
    "                for child in cur.children:\n",
    "                    que.append(child)\n",
    "            res1.append(res2)\n",
    "        return res1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "import queue\n",
    "class Solution(object):\n",
    "    def levelOrder(self, root):\n",
    "        \"\"\"\n",
    "        :type root: Node\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return None\n",
    "        elif not root.children:\n",
    "            return [[root.val]]\n",
    "\n",
    "        q = queue.SimpleQueue()\n",
    "        retArr = []\n",
    "        q.put(root)\n",
    "        children = []\n",
    "        while not q.empty():\n",
    "            children = []\n",
    "            for i in range(q.qsize()):\n",
    "                elem = q.get()\n",
    "                children.append(elem.val)\n",
    "                if elem.children:\n",
    "                    for child in elem.children:\n",
    "                        q.put(child)\n",
    "\n",
    "            retArr.append(children)\n",
    "\n",
    "        # print(retArr)\n",
    "\n",
    "        return retArr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def levelOrder(self, root: 'Node') -> list[list[int]]:\n",
    "        \"\"\"\n",
    "        思路: 使用广度搜索\n",
    "\n",
    "        维护一个双端队列 队列中只存储当前层级的节点\n",
    "\n",
    "        遍历队列\n",
    "        - 每次开始时 记录当前队列中的元素总量 即当前层级的节点总数\n",
    "        - 维护一个level级别的列表 每次将同一层级节点的元素追加进来\n",
    "        - 遍历每个节点的子节点 将其加入到队列的尾端 准备进行下一轮遍历\n",
    "        \"\"\"\n",
    "        results = list()\n",
    "        if not root:\n",
    "            return results\n",
    "        \n",
    "        # 定义双端队列\n",
    "        double_quue = list()\n",
    "        double_quue.append(root)\n",
    "\n",
    "        while double_quue:\n",
    "\n",
    "            level_list = list()\n",
    "\n",
    "            current_level_no = len(double_quue)\n",
    "\n",
    "            for index in range(0, current_level_no):\n",
    "                level_list.append(double_quue[index].val)\n",
    "\n",
    "                for ch in double_quue[index].children:\n",
    "                    double_quue.append(ch)\n",
    "\n",
    "            double_quue = double_quue[current_level_no:]\n",
    "\n",
    "            results.append(level_list)\n",
    "\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'Node') -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = collections.deque([root])\n",
    "        result = []\n",
    "        while queue:\n",
    "            level = []\n",
    "            for _ in range(len(queue)):\n",
    "                cur = queue.pop()\n",
    "                level.append(cur.val)\n",
    "                for child in cur.children:\n",
    "                    queue.appendleft(child)\n",
    "            result.append(level)\n",
    "        \n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'Node') -> List[List[int]]:\n",
    "        level = 0\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        if not root:\n",
    "            return []\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            ceng = []\n",
    "            while size:\n",
    "                size -= 1\n",
    "                # print(size) \n",
    "                node= queue.popleft()\n",
    "                if not node:\n",
    "                    continue\n",
    "                ceng.append(node.val)\n",
    "                for i in node.children:\n",
    "                    queue.append(i)\n",
    "                # queue.append(node.right)\n",
    "            res.append(ceng)\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
